package com.hdu.other.monotonyQueue;

public class lc1499 {
    class Solution {
        public int findMaxValueOfEquation(int[][] points, int k) {
            /*
             * 请你找出 yi + yj + |xi - xj| 的 最大值，其中 |xi - xj| <= k 且 1 <= i < j <= points.length。
             * xj - xi + yi + yj
             * yi - xi + xj + yj
             */
            int len = points.length;
            int[] q = new int[len];
            int h = 0, t = 0;
            int ans = Integer.MIN_VALUE;
            for (int j = 0; j < len; j++) {
                int xj = points[j][0];
                int yj = points[j][1];

                // 淘汰掉过期的
                while (h < t && xj - points[q[h]][0] > k) {
                    h++;
                }

                if (h < t) {
                    ans = Math.max(
                            ans,
                            xj + yj + points[q[h]][1] - points[q[h]][0]
                    );
                }

                while (h < t && yj - xj >= points[q[t - 1]][1] - points[q[t - 1]][0]) {
                    t--;
                }

                q[t++] = j;
            }

            return ans;
        }
    }
}
